package codingStudy.Dynamic.Fibonacci;

import java.util.Scanner;

/**
 * @author dell
 * @category 动态规划版本
 */
public class Bate3 {
	private static int[] money;

	static int fio(int x) {
		money = new int[x + 1];
		money[0] = 0;
		money[1] = 1;
		for (int i = 2; i < x + 1; i++) {
			money[i] = money[i - 1] + money[i - 2];
		}
		return money[x];

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tage = sc.nextInt();
		long start = System.currentTimeMillis();
		int result = fio(tage);
		long end = System.currentTimeMillis();
		long time = end - start;
		System.out.println(result + " " + time + "");
	}

}
